package hotLeetcode;

public class H105Leetcode {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder, inorder, 0, 0, inorder.length - 1);

    }

    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
        if (inStart > inEnd) return null;


        //前序遍历的第一个元素就是根节点
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        //找到根节点在中序遍历中的位置
        int rootIndexInInorder = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIndexInInorder = i;
                break;
            }
        }

        // 左子树大小
        int leftSubtreeSize = rootIndexInInorder - inStart;
        //递归构建左子树
        root.left = buildTreeHelper(preorder, inorder, preStart + 1, inStart, rootIndexInInorder - 1);
        //构建右子树
        root.right = buildTreeHelper(preorder, inorder, preStart + leftSubtreeSize + 1, rootIndexInInorder + 1, inEnd);



        return root;
    }
}
